Asynchronous Cellular Automata in Erlang

Cells in a Cellular Automata are normally defined as

For this experiment I chose to relax the last condition. Instead each cell is modeled as a separate process in the Erlang programming language. Erlang is unique in its support of very large numbers of lightweight application-level processes. Instead of using shared memory, the processes communicate solely through message passing. Here each cell is aware of and communicates with its six local neighbors, plus a common process used to log state to disk (for display in a C/OpenGL program). The processes react to received messages or a timer message, and wait a period of time before forwarding messages to neighbors or decaying their current state. This wait can vary depending on when the process is scheduled on the CPU. The timers only guarantee a minimum wait time, not a maximum wait.

The testing was performed on a AMD Athlon A64x2 (dual-core) 4400 CPU (2.2 GHz), 2G Memory. The automata size was 50x50x50 cells, or 125,000 processes. The program ran much slower with 2 cores active, and going over 125,000 processes also overwhelmed the CPU (probably too many timer interrupts).

The progress of the patterns across the automata was uneven, demonstrating the interaction of the asynchronous behavior with the Erlang process scheduling algorithm. Unlike a synchronous automata, there is no "correct" order of evaluation of processes. The logging processes acts as an observer, and does log messages in order of receipt, but does not force a global ordering of execution across the system.

Asynchronous automata may more accurately model many phenomena in both nature and artificial systems.

Erlang code is here.

C/OpenGL display code is here.

Last tested on:

Erlang R13B03 (erts-5.7.4) [source] [64-bit] [smp:12:12] [rq:12] [async-threads:0] [hipe] [kernel-poll:false]
Linux hex 2.6.35-25-generic #44-Ubuntu SMP Fri Jan 21 17:40:44 UTC 2011 x86_64 GNU/Linux
gcc version 4.4.5 (Ubuntu/Linaro 4.4.4-14ubuntu5)
"DimSize = 50" currently gives "Too many processes" error, so reduce to 25 in acell.erl.

First start the Erlang program acell.erl:

This will start writing outfile.txt, which contains lines of the form x,y,z:red,green,blue. Now run acell.c in another shell (note compilation will probably require installing additional Debian packages such as GLEW, GLUT, etc.):
gcc acell.c -lGLEW -lGL -lGLU -lglut -lm -O3 -o acell
./acell outfile.txt
This will bring up a viewer window and print a set of instuctions:
turn step =   5.73 degrees
move_step =   4.00

h == turn left
l == turn right
k == move forward
j == move backward
mouse == turn left,
         turn right,
         look down,
         look up
r == toggle run
n == next (single step)
w == increment W dimension
q == QUIT
Type "n" repeatedly to advance time.

When finished don't forget to ^C (a)bort acell.erl, as it is still appending to outfile.txt.

See also Multi-Core Ant Colony Optimization for TSP in Erlang.